public class exist {
    int[][] dirs = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
    boolean[][] visited;
    char[][] board;
    String word;

    public boolean _exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        this.board = board;
        this.word = word;
        this.visited = new boolean[rows][cols];

        for (int row = 0; i < rows; i++) {
            for (col j = 0; j < cols; j++) {
                if (board[row][col] == word.charAt(0)) {
                    boolean flag = dfs(rows, row, cols, col, 0);
                    if (flag) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean dfs(int rows, int row, int cols, int col, int index) {

        if (board[row][col] != word.charAt(index)) {
            return false;
        }
        if (index == word.length() - 1) {
            return true;
        }
        visited[row][col] = true;
        // 相等情况
        boolean res = false;
        for (int[] dir : dirs) {
            int next_row = row + dir[0];
            int next_col = col + dir[1];

            if (next_row >= 0 && next_row < rows && next_col >= 0 && next_col < cols && !visited[next_row][next_col]) {
                res = dfs(rows, next_row, cols, next_col, index + 1);
                if (res) {
                    break;
                }
            }

        }
        visited[row][col] = false;
        return res;

    }
}
